home *** CD-ROM | disk | FTP | other *** search
/ NetNews Offline 2 / NetNews Offline Volume 2.iso / news / comp / lang / c-part2 / 12530 < prev    next >
Encoding:
Internet Message Format  |  1996-08-05  |  2.1 KB
  1. Path: keats.ugrad.cs.ubc.ca!not-for-mail
  2. From: c2a192@ugrad.cs.ubc.ca (Kazimir Kylheku)
  3. Newsgroups: comp.lang.c
  4. Subject: Re: "Best fit" algorithm (help)
  5. Date: 1 Apr 1996 07:06:39 -0800
  6. Organization: Computer Science, University of B.C., Vancouver, B.C., Canada
  7. Message-ID: <4jordvINNi5m@keats.ugrad.cs.ubc.ca>
  8. References: <APC&7'0'22b6b83'874@peg.apc.org> <4ji4b1$jc5@news1.mnsinc.com> <4jnq7t$643@airdmhor.gen.nz> <4jop2g$m9p@news1.mnsinc.com>
  9. NNTP-Posting-Host: keats.ugrad.cs.ubc.ca
  10.  
  11. In article <4jop2g$m9p@news1.mnsinc.com>,
  12. Szu-Wen Huang <huang@mnsinc.com> wrote:
  13.  >Simon Hosie (gumboot@airdmhor.gen.nz) wrote:
  14.  >
  15.  >: Szu-Wen Huang:
  16.  >: > The solution to the knapsack problem is to randomly allocate?!  I'm
  17.  >: > fairly sure my algorithm teacher doesn't know this yet.  Care to show
  18.  >: > some numbers?  *Chuckle*
  19.  >
  20.  >:   He said it was faster than brute force.  I couldn't be bothered writing my
  21.  >: own so I just accepted it.  It's got me curious, now, I think I might have a
  22.  >: go at it.
  23.  >
  24.  >The knapsack problem has a large search space, and is NP I think.  That
  25.  >generally means a random search won't get you very far.
  26.  
  27. But the problem at hand is _not_ a knapsack problem! It is a cousin of the
  28. knapsack problem. In the real knapack problem, you have to find a subset of a
  29. given set of integers such that they sum _precisely_ to a given value.
  30.  
  31. In this problem, the subset has to form a sum _less than or equal_ to a given
  32. value (the length of the tape). Thus many solutions are acceptable, with some
  33. being better than others. Some sort of acceptable threshold can be set for what
  34. is an acceptable amount of wasted space left on the tape. A random mixing could
  35. turn up solutions, especially when the set of songs is not that large.
  36.  
  37. If you think about it, a human could solve this problem without mechanically
  38. seaching a large space in NP time. Many people successfully put together audio
  39. tapes without even knowing what an algorithm is! :)
  40.  
  41. On a slow, 8-bit machine (such as the C-64), your computing power and amount of
  42. memory is limited (though, as I recall, that didn't prevent Sargon II running
  43. on an 8-bit machine from playing a mean game of chess!!!).
  44. -- 
  45.  
  46.